import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-24
 * Time: 22:14
 */

class Solution {
    // 思路:
    // 前缀和 + 哈希优化

    // 需要考虑的问题:
    // 1. 前缀和本身就 ==k
    // 2. k==0时,如果使用map记录完前缀和再进行查找符合的结果
    //    会多记录自身, 不只是自身, 是 * 所有与自身相等的个数
    public int subarraySum(int[] nums, int k) {
        int count=0;
        int prefix=0;
        Map<Integer, Integer> map=new HashMap<>();
        map.put(0,1);  // 解决了 问题一: 前缀和本身就 ==k
        for(int x: nums){
            prefix+=x;
            // 巧妙的解决了问题二: 一边记录前缀和, 一边进行查找,
            // 记录的同时进行查找, k==0 时, 不会记录自身
            // 既解决了问题, 又减少了因 两次遍历 所需要的时间以及空间
            if(map.containsKey(prefix-k)){
                count+=map.get(prefix-k);
            }
            map.put(prefix, map.getOrDefault(prefix, 0)+1);
        }
        return count;
    }
}
